//水果成篮
class Solution {
public:
    int totalFruit(vector<int>& nums) {
        unordered_map<int,int> hash;
        int left = 0 , right = 0 , n = nums.size(),ret = 0;

        
        while(right < n )
        {
            if(!hash.count(nums[right]))
            {
                if(hash.size() == 2)
                {
                    int& temp = hash[nums[left]];
                    temp--;
                    if(temp == 0)
                    {
                        hash.erase(nums[left]);
                        hash.insert({nums[right++],1});
                    }
                    ++left;
                }
                else 
                {
                    hash.insert({nums[right++],1});
                }

            }
            else 
            {
                hash[nums[right]]++;
                ++right;
            }
            ret = max(right - left , ret);
        }
        return ret;
    }
};

//找到字符串中所有字母异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> hash1(26); //统计窗口中字符出现的个数
        vector<int> hash2(26); //统计目标p中字符出现的个数
        vector<int> ret;//结果数组
        for(auto& e : p)
        {
            hash2[e-'a']++;
        }
        int m = p.size();
        //count统计窗口中有效字符的个数
        for(int left = 0 , right = 0 , count = 0 ; right < s.size() ; ++right)
        {
            //进窗口 + 维护count
            char in = s[right];
            if(++hash1[in-'a'] <= hash2[in - 'a']) count++;
            //判断
            if(right - left + 1 > m)
            {
                //出窗口 + 维护count
                char out = s[left++];
                if(hash1[out - 'a']-- <= hash2[out - 'a']) count--;
            }
            //更新结果
            if(count == m) ret.push_back(left);
        }
        return ret;
    }
};

//串联所有单词的子串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2; // 统计words中的单词
        for (auto& s : words) {
            hash2[s]++;
        }
        vector<int> ret;
        // count是窗口中有效字符串的个数
        int len = words.size(), wordSize = words[0].size();
        for (int i = 0; i < wordSize; ++i) {
            unordered_map<string, int> hash1; // 统计窗口中的单词
            for (int left = i, right = i, count = 0; right < s.size();
                 right += wordSize) {
                // 进窗口 + 维护count
                string in = s.substr(right, wordSize);
                if (++hash1[in] <= hash2[in])
                    count++;

                // 判断
                if (right - left + 1 > wordSize * len) {
                    // 出窗口 + 维护count
                    string out = s.substr(left, wordSize);
                    if (hash1[out]-- <= hash2[out])
                        count--;
                    left += wordSize;
                }

                // 更新结果
                if (count == len)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};

//最小覆盖子串
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> hash1;//统计窗口中字符出现的个数
        unordered_map<char,int> hash2;//统计目标字符出现的个数
        for(auto& ch : t)
        {
            hash2[ch]++;
        }
        string ret;
        int m = t.size();
        for(int left = 0 , right = 0 , count = 0 ; right < s.size() ; ++right)
        {
            //进窗口 + 维护count
            char in = s[right];
            if(++hash1[in] <= hash2[in]) ++count;

            //判断
            while(count == m)
            {
                //更新结果
                string temp = s.substr(left,right-left+1);
                if(ret.size() == 0 || ret.size() > temp.size()) ret = temp;

                //出窗口 + 维护count
                char out = s[left++];
                if(hash1[out]-- <= hash2[out]) --count;
            }
        }
        return ret;
    }
};
